/*
 ** SimpleList.java
 */
package jrpdk.util;

import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.AbstractSequentialList;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;

/**
 ** Liste chaenee d'elements simplifiee. Cette liste est particulierement efficasse en terme de memoire et de temps sur
 * les operations simples.
 */
public class SimpleList<E> extends AbstractSequentialList<E> implements List<E>, Cloneable, java.io.Serializable {
    private static final long  serialVersionUID    = 1L;

    private SimpleListEntry<E> firstItem;
    private SimpleListEntry<E> lastItem;
    private int                size;
    private int                modificationCounter = 0;

    /**
**
*/
    public SimpleList() // ----------------------------------------------------
    {
        this( null );
    }

    /**
**
*/
    public SimpleList( // -----------------------------------------------------
            final SimpleListEntry<E> firstEntry )
    {
        if( firstEntry == null ) {
            this.lastItem = this.firstItem = null;
            this.size = 0;
        } else {
            this.firstItem = firstEntry;

            int count = 1;
            SimpleListEntry<E> prev = firstEntry;
            SimpleListEntry<E> node = firstEntry.next;

            while( node != null ) {
                prev = node;
                node = node.next;
                count++;
            }

            this.lastItem = prev;
            this.size = count;
        }
    }

    /**
     ** @return the SimpleListEntry at the specified position in this list.
     */
    private SimpleListEntry<E> getSimpleListEntry( final int index ) // -----------------
    {
        if( (index < 0) || (index >= this.size) ) {
            throw new IndexOutOfBoundsException( "Index: " + index + ", Size: " + this.size );
        }

        SimpleListEntry<E> e = this.firstItem;

        for( int i = 0; i <= index; i++ ) {
            e = e.next;
        }

        return e;
    }

    // /**
    // ** @return the previous SimpleListEntry that specify.
    // */
    // private SimpleListEntry<E> getPrevSimpleListEntry( // ------------------------
    // SimpleListEntry<E> entry
    // )
    // {
    // SimpleListEntry<E> prev = null;
    //
    // for( SimpleListEntry<E> e = firstItem; e != null; e = e.next ) {
    //
    // if( e == entry ) {
    // return prev;
    // }
    //
    // prev = e;
    // }
    //
    // throw new InternalError( "entry not found." );
    // }

    /**
**
*/
    @Override
    public void add( final int index, final E o ) // ---------------------------------
    {
        if( (index < 0) || (index > this.size) ) {
            throw new IndexOutOfBoundsException( "Index: " + index + ", Size: " + this.size );
        }

        if( index == 0 ) { // Ajout en tete
            addFirst( o );

            return;
        }

        if( index == this.size ) { // Ajout en queue
            add( o );

            return;
        }

        // Recherche de la position
        final SimpleListEntry<E> prev = getSimpleListEntry( index - 1 );

        // Insertion d'une nouvelle entree.
        prev.next = new SimpleListEntry<E>( o, prev.next );

        this.size++;
        this.modificationCounter++;
    }

    /**
     ** Appends the specified element to the end of this list.
     */
    @Override
    public boolean add( final E o ) // -----------------------------------------
    {
        if( this.firstItem == null ) {
            // list vide
            this.lastItem = this.firstItem = new SimpleListEntry<E>( o );
        } else {
            // this.firstItem = [NO CHANGE];
            this.lastItem = new SimpleListEntry<E>( o, this.lastItem );
        }

        this.modificationCounter++;
        this.size++;

        return true;
    }

    /**
     ** Inserts the given element at the beginning of this list.
     **
     ** @param o
     *            the element to be inserted at the beginning of this list.
     */
    public void addFirst( final E o ) // ---------------------------------------
    {
        if( this.firstItem == null ) {
            // list vide
            this.lastItem = this.firstItem = new SimpleListEntry<E>( o );
        } else {
            this.firstItem = new SimpleListEntry<E>( o, this.firstItem );
            // this.lastItem = [NO CHANGE];
        }

        this.modificationCounter++;
        this.size++;
    }

    // public boolean _addAll( Collection c ){} // ----------------------------------
    // public boolean _addAll( int index, Collection c ){} // -----------------------

    /**
     ** Removes all of the elements from this list
     */
    @Override
    public void clear() // ----------------------------------------------------
    {
        this.lastItem = this.firstItem = null;
        this.size = 0;
        this.modificationCounter++;
    }

    /**
     ** Returns true if this list contains the specified element. More formally, returns true if and only if this list
     * contains at least one element e such that (o==null ? e==null : o.equals(e)).
     **
     ** @param o
     *            element whose presence in this list is to be tested.
     **
     ** @return true if this list contains the specified element.
     */
    @Override
    public boolean contains( final Object o ) // ------------------------------------
    {
        return indexOf( o ) != -1;
    }

    // public boolean _containsAll(Collection c)

    /**
     ** Returns the element at the specified position in this list.
     **
     ** @param index
     *            index of element to return.
     ** @return the element at the specified position in this list.
     **
     ** @throws IndexOutOfBoundsException
     *             if the specified index is is out of range (<tt>index &lt; 0 || index &gt;= size()</tt>).
     */
    @Override
    public E get( final int index ) // -----------------------------------------
    {
        return getSimpleListEntry( index ).element;
    }

    /**
     ** Replaces the element at the specified position in this list with the specified element.
     **
     ** @param index
     *            index of element to replace.
     ** @param element
     *            element to be stored at the specified position.
     ** @return the element previously at the specified position.
     ** @throws IndexOutOfBoundsException
     *             if the specified index is out of range (<tt>index &lt; 0 || index &gt;= size()</tt>).
     */
    @Override
    public E set( final int index, final E element )
    {
        final SimpleListEntry<E> e = getSimpleListEntry( index );
        final E oldVal = e.element;

        e.element = element;

        //
        // Pas de modification de "this.modificationCounter", car la
        // structure de la liste n'a pas changee.
        //

        return oldVal;
    }

    /**
     ** Returns the index in this list of the first occurrence of the specified element, or -1 if the List does not
     * contain this element. More formally, returns the lowest index i such that
     ** <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if there is no such index.
     **
     ** @param o
     *            element to search for.
     ** @return the index in this list of the first occurrence of the specified element, or -1 if the list does not
     *         contain this element.
     */
    @Override
    public int indexOf( final Object o ) // -----------------------------------------
    {
        int index = 0;

        if( o == null ) {
            for( SimpleListEntry<E> e = this.firstItem; e != null; e = e.next ) {
                if( e.element == null ) {
                    return index;
                }
                index++;
            }
        } else {
            for( SimpleListEntry<E> e = this.firstItem; e != null; e = e.next ) {
                if( o.equals( e.element ) ) {
                    return index;
                }
                index++;
            }
        }

        return -1;
    }

    /**
     ** @return an iterator over the elements in this list in proper sequence.
     */
    @Override
    public Iterator<E> iterator() // ---------------------------------------------
    {
        return new SLIterator();
    }

    // public int _lastIndexOf(Object o)
    // public ListIterator _listIterator()

    /**
     ** Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in
     * the list. Obeys the general contract of <tt>List.listIterator(int)</tt>.
     * <p>
     *
     * The list-iterator is <i>fail-fast</i>: if the list is structurally modified at any time after the Iterator is
     * created, in any way except through the list-iterator's own <tt>remove</tt> or <tt>add</tt> methods, the
     * list-iterator will throw a <tt>ConcurrentModificationException</tt>. Thus, in the face of concurrent
     * modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior
     * at an undetermined time in the future.
     **
     ** @param index
     *            index of first element to be returned from the list-iterator (by a call to <tt>next</tt>).
     ** @return a ListIterator of the elements in this list (in proper sequence), starting at the specified position in
     *         the list.
     ** @throws IndexOutOfBoundsException
     *             if index is out of range (<tt>index &lt; 0 || index &gt; size()</tt>).
     ** @see List#listIterator(int)
     */
    @Override
    public ListIterator<E> listIterator( final int index ) // --------------------
    {
        return new SLListIterator( index );
    }

    // public Object _remove(int index)

    @SuppressWarnings("null")
    @Override
    public boolean remove( final Object o ) // --------------------------------------
    {
        System.out.println( "public boolean remove( Object o )" );
        if( this.size == 0 ) {
            return false; // liste vide
        }

        if( o == null ) {
            if( this.firstItem.element == null ) {
                removeFirst();
                return true;
            }

            if( this.lastItem.element == null ) {
                removeLast();
                return true;
            }

            SimpleListEntry<E> prev = null;

            for( SimpleListEntry<E> e = this.firstItem; e != null; e = e.next ) {

                if( e.element == null ) {
                    // il ne s'agit ni du premier, ni du dernier element.
                    prev.next = e.next;
                    this.size--;

                    return true;
                }

                prev = e;
            }

            return false;
        } else { // o != null

            if( o.equals( this.firstItem.element ) ) {
                removeFirst();
                return true;
            }

            if( o.equals( this.lastItem.element ) ) {
                removeLast();
                return true;
            }

            SimpleListEntry<E> prev = null;

            for( SimpleListEntry<E> e = this.firstItem; e != null; e = e.next ) {
                if( o.equals( e.element ) ) {
                    // il ne s'agit ni du premier, ni du dernier element.
                    prev.next = e.next;
                    this.size--;

                    return true;
                }

                prev = e;
            }
            return false;
        }
    }

    @SuppressWarnings("null")
    private void removeSimpleListEntry( final SimpleListEntry<E> entry ) // ------------
    {
        if( this.firstItem == entry ) {
            removeFirst();
            return;
        }

        if( this.lastItem.element == entry ) {
            removeLast();
            return;
        }

        SimpleListEntry<E> prev = null;

        for( SimpleListEntry<E> e = this.firstItem; e != null; e = e.next ) {
            if( e == entry ) {
                // il ne s'agit ni du premier, ni du dernier element.
                prev.next = e.next;
                this.size--;

                return;
            }

            prev = e;
        }

        throw new NoSuchElementException();
    }

    // public boolean _removeAll(Collection c)
    // public boolean _retainAll(Collection c)

    /**
     ** Returns the number of elements in this list.
     **
     ** @return the number of elements in this list.
     */
    @Override
    public int size() // ------------------------------------------------------
    {
        return this.size;
    }

    // public List subList( int fromIndex, int toIndex )
    // public Object[] _toArray()
    // public Object[] _toArray(Object[] a)

    /**
     ** Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts
     * one from their indices). Returns the element that was removed from the list.
     **
     ** @param index
     *            the index of the element to removed.
     **
     ** @return the element previously at the specified position.
     **
     ** @throws IndexOutOfBoundsException
     *             if the specified index is out of range (<tt>index &lt; 0 || index &gt;= size()</tt>).
     */
    @SuppressWarnings("null")
    @Override
    public E remove( final int index ) // --------------------------------------
    {
        System.out.println( "public boolean remove( int index )" );

        if( (index < 0) || (index >= this.size) ) {
            throw new IndexOutOfBoundsException( "Index: " + index + ", Size: " + this.size );
        }

        if( index == 0 ) {
            return removeFirst();
        }

        if( (index - 1) == this.size ) {
            return removeLast();
        }

        SimpleListEntry<E> prev = null;
        SimpleListEntry<E> e = this.firstItem;

        for( int i = 0; i <= index; i++ ) {
            prev = e;
            e = e.next;
        }

        // Note: il ne s'agit ni de la tete, ni de la queue.

        prev.next = e.next;

        this.size--;
        this.modificationCounter++;

        return e.element;
    }

    /**
     ** Removes and returns the first element from this list.
     **
     ** @return the first element from this list.
     **
     ** @throws NoSuchElementException
     *             if this list is empty.
     */
    public E removeFirst() // --------------------------------------------
    {
        System.out.println( "public Object removeFirst()" );

        final SimpleListEntry<E> first = this.firstItem;

        if( first == null ) {
            throw new NoSuchElementException();
        }

        if( this.size == 1 ) {
            this.lastItem = this.firstItem = null;
            this.size = 0;
        } else {
            this.firstItem = first.next;

            this.size--;
        }

        this.modificationCounter++;

        return first.element;
    }

    /**
     ** Removes and returns the last element from this list.
     **
     ** @return the last element from this list.
     ** @throws NoSuchElementException
     *             if this list is empty.
     */
    public E removeLast() // ---------------------------------------------
    {
        System.out.println( "public Object removeLast()" );

        final SimpleListEntry<E> last = this.lastItem;

        if( last == null ) {
            throw new NoSuchElementException();
        }

        if( this.size == 1 ) {
            // il n'y a qu'un element dans la liste
            this.lastItem = this.firstItem = null;
            this.size = 0;
        } else if( this.size == 2 ) {
            // il n'y a que deux elements dans la liste
            this.lastItem = this.firstItem;
            this.size = 1;
        } else {
            this.lastItem = getSimpleListEntry( this.size - 2 );

            this.size--;
        }

        this.modificationCounter++;

        return last.element;
    }

    /**
     ** Returns a shallow copy of this <tt>SimpleList</tt>. (The elements themselves are not cloned.)
     **
     ** @return a shallow copy of this <tt>SimpleList</tt> instance.
     */
    @Override
    public Object clone() // --------------------------------------------------
    {
        try {
            @SuppressWarnings("unchecked")
            final SimpleList<E> clone = (SimpleList<E>)super.clone();

            // Initialize clone
            clone.firstItem = null;
            clone.lastItem = null;
            clone.size = 0;
            clone.modificationCounter = 0;

            // Read in all elements in the proper order.
            for( SimpleListEntry<E> e = this.firstItem.next; e != null; e = e.next ) {
                clone.add( e.element );
            }

            return clone;
        }
        catch( final CloneNotSupportedException e ) {
            throw new InternalError();
        }
    }

    /**
     ** Save the state of this <tt>SimpleList</tt> instance to a stream (that is, serialize it).
     **
     ** @serialData The size of the list (the number of elements it contains) is emitted (int), followed by all of its
     *             elements (each an Object) in the proper order.
     */
    private synchronized void writeObject( final ObjectOutputStream s ) // --
            throws java.io.IOException
    {
        // Write out any hidden serialization magic
        s.defaultWriteObject();

        // Write out size
        s.writeInt( this.size );

        // Write out all elements in the proper order.
        for( SimpleListEntry<E> e = this.firstItem.next; e != null; e = e.next ) {
            s.writeObject( e.element );
        }
    }

    /**
     ** Reconstitute this <tt>SimpleList</tt> instance from a stream (that is deserialize it).
     */
    private synchronized void readObject( final ObjectInputStream s ) // ----
            throws java.io.IOException, ClassNotFoundException
    {
        // Read in any hidden serialization magic
        s.defaultReadObject();

        // Read in size
        final int size = s.readInt();

        // Initialize
        this.firstItem = null;
        this.lastItem = null;
        this.size = 0;
        this.modificationCounter = 0;

        // Read in all elements in the proper order.
        for( int i = 0; i < size; i++ ) {
            @SuppressWarnings("unchecked")
            final
            E e = (E)(s.readObject());
            add( e );
        }
    }

    /**
    **
    */
    private class SLIterator implements Iterator<E> {
        protected SimpleListEntry<E> currentEntry;
        protected int                currentEntryIndex;
        protected int                iteratorMC;
        protected SimpleListEntry<E> lastReturn;

        public SLIterator() // ------------------------------------------------
        {
            this.currentEntry = SimpleList.this.firstItem;
            this.currentEntryIndex = 0;
            this.iteratorMC = SimpleList.this.modificationCounter;
            this.lastReturn = null;
        }

        @Override
        public boolean hasNext() // -------------------------------------------
        {
            return this.currentEntry != null;
        }

        @Override
        public E next() // -----------------------------------------------
        {
            final SimpleListEntry<E> result = this.currentEntry;

            if( this.iteratorMC != SimpleList.this.modificationCounter ) {
                throw new ConcurrentModificationException();
            }

            try {
                this.currentEntry = this.currentEntry.next;
            }
            catch( final NullPointerException e ) {
                throw new NoSuchElementException();
            }

            this.lastReturn = result;
            this.currentEntryIndex++;

            return result.element;
        }

        @Override
        public void remove() // -----------------------------------------------
        {
            if( this.lastReturn == null ) {
                throw new IllegalStateException();
            }

            if( this.iteratorMC != SimpleList.this.modificationCounter ) {
                throw new ConcurrentModificationException();
            }

            SimpleList.this.removeSimpleListEntry( this.lastReturn );

            --this.currentEntryIndex; // La position courante a bougee d'un element

            this.lastReturn = null;
            this.iteratorMC = SimpleList.this.modificationCounter;
        }

    } // inner-class SLIterator

    /**
    **
    */
    private class SLListIterator extends SLIterator implements ListIterator<E> {
        private int                currentIndex;
        private int                iteratorMC;
        private SimpleListEntry<E> lastReturned;
        private SimpleListEntry<E> lastReturnedNext;

        public SLListIterator( final int index ) // ---------------------------------
        {
            this.currentIndex = index;
            this.iteratorMC = SimpleList.this.modificationCounter;
            this.lastReturned = null;
            this.lastReturnedNext = null;
        }

        @Override
        public void add( final E o ) // ----------------------------------------
        {
            synchronized( SimpleList.this ) {
                if( this.iteratorMC != SimpleList.this.modificationCounter ) {
                    throw new ConcurrentModificationException();
                }

                SimpleList.this.add( this.currentIndex, o );

                this.currentIndex++; // on a ajoute avant le curseur
                this.iteratorMC = SimpleList.this.modificationCounter;
            }

            this.lastReturned = this.lastReturnedNext = null;
        }

        @Override
        public boolean hasNext() // ---------------------------------------
        {
            return this.currentIndex < SimpleList.this.size;
        }

        @Override
        public boolean hasPrevious() // -----------------------------------
        {
            return this.currentIndex > 0;
        }

        @Override
        public E next() // -------------------------------------------
        {
            if( this.iteratorMC != SimpleList.this.modificationCounter ) {
                throw new ConcurrentModificationException();
            }

            final SimpleListEntry<E> entry = getSimpleListEntry( this.currentIndex++ );
            E value;

            try {
                value = entry.element;
            }
            catch( final NullPointerException e ) {
                throw new NoSuchElementException();
            }

            this.lastReturned = entry;
            this.lastReturnedNext = entry.next;

            return value;
        }

        @Override
        public int nextIndex() // -----------------------------------------
        {
            return this.currentIndex;
        }

        @Override
        public E previous() // ---------------------------------------
        {
            if( this.iteratorMC != SimpleList.this.modificationCounter ) {
                throw new ConcurrentModificationException();
            }

            if( this.currentIndex == 0 ) {
                throw new NoSuchElementException();
            }

            final SimpleListEntry<E> entry = getSimpleListEntry( --this.currentIndex );
            final E value = entry.element;

            this.lastReturnedNext = this.lastReturned = entry;

            return value;
        }

        @Override
        public int previousIndex() // -------------------------------------
        {
            return this.currentIndex - 1;
        }

        @Override
        public void remove() // -------------------------------------------
        {
            synchronized( SimpleList.this ) {
                if( this.iteratorMC != SimpleList.this.modificationCounter ) {
                    throw new ConcurrentModificationException();
                }

                if( this.lastReturned == null ) {
                    throw new IllegalStateException();
                }

                if( this.lastReturnedNext != this.lastReturned ) {
                    --this.currentIndex;
                }

                SimpleList.this.remove( this.lastReturned );

                this.iteratorMC = SimpleList.this.modificationCounter;
            }

            this.lastReturned = this.lastReturnedNext = null;
        }

        @Override
        public void set( final E o ) // ------------------------------------
        {
            if( this.iteratorMC != SimpleList.this.modificationCounter ) {
                throw new ConcurrentModificationException();
            }

            if( this.lastReturned == null ) {
                throw new IllegalStateException();
            }

            this.lastReturned.element = o;
            this.lastReturned = null;
        }
    }

    // public static void main( String[] args ) // -------------------------------
    // {
    // SimpleList<String> instance
    // = new SimpleList<String>(
    // new SimpleListEntry<String>( "1",
    // new SimpleListEntry<String>( "2",
    // new SimpleListEntry<String>( "3",
    // new SimpleListEntry<String>( "4",
    // new SimpleListEntry<String>( "5" )
    // )
    // )
    // )
    // )
    // );
    //
    // System.out.print( "LIST( " );
    // int skip = 3;
    //
    // for( Iterator<String> iter = instance.iterator(); iter.hasNext(); ) {
    // System.out.print( " " + iter.next() + "," );
    //
    // if( skip == 0 ) {
    // iter.remove();
    // }
    // else {
    // skip--;
    // }
    // }
    //
    // System.out.println( " END )" + instance.size() );
    //
    // System.out.print( "LIST( " );
    //
    // for( Iterator<String> iter = instance.iterator(); iter.hasNext(); ) {
    // System.out.print( " " + iter.next() + "," );
    // }
    //
    // System.out.println( " END )" + instance.size() );
    //
    // System.out.print( "LIST( " );
    //
    // for( ListIterator<?> iter = instance.listIterator( 0 ); iter.hasNext(); ) {
    // System.out.print( " " + iter.next() + "," );
    // }
    // System.out.println( " END )" );
    //
    //
    // System.out.print( "LIST( " );
    // for( ListIterator<?> iter = instance.listIterator( 0 ); iter.hasPrevious(); ) {
    // System.out.print( " " + iter.previous() + "," );
    // }
    // System.out.println( " END )" );
    // }

} // class

